lintcode 倒水

Posted on | In

lintcode 倒水

描述

给定一个评估图， heights[i] 表示该地的高度。所有下标对应的地面宽度均为 1。请问V个单位的水落在下标为 K 的地面之后，每个下标对应的地面水量是多少？

水首先从下标K降落，接着它依据下述规则流动：

首先，液滴不能流向更高的地方；
如果液滴能向左最终能下降，那么向左移动；
否则，如果能向右最终能下降，则向右移动；
否则，留当前位置。
其中，“最终能下降”意味着如果液滴像那个方向移动，最终能够处于更低高度。

假设整个区域左右两侧有无限高的地形。此外，一单位水不能拆分，即每个单位必须恰好落在一个区块内。

样例

输入: heights = [1,2,3,4], V = 2, K = 2
输出: [2,3,3,4]
解释: 最后一滴水落到位置1，因为继续往左走不会下降。

输入: heights = [3,1,3], V = 5, K = 1
输出: [4,4,4]

思路

实现两个函数，往左检索找水滴的位置和往右检索找水滴的位置，如果水滴没有可以放的地方就返回-1
如果两次都返回-1那么就在原地

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    /**
     * @param heights: the height of the terrain
     * @param V: the units of water
     * @param K: the index
     * @return: how much water is at each index
     */

    int find_min_left(vector<int> heights, int K) {
        int index = -1, min = heights[K];
        for (int i = K-1; i >=0; i--) {

            if (heights[i] < min) {
                index = i;
                min = heights[i];
            }

            if (heights[i] > min)
                break;
        }
        return index;
    }

    int find_min_right(vector<int> heights, int K) {
        int index = -1, min = heights[K];
        for (int i = K+1; i <heights.size(); i++) {

            if (heights[i] < min) {
                index = i;
                min = heights[i];
            }

            if (heights[i] > min)
                break;
        }
        return index;

    }

    vector<int> pourWater(vector<int> &heights, int V, int K) {
        // Write your code here
        bool flag_left = true, flag_self = false;
        for (int i = 0; i < V; i++) {

            int index = find_min_left(heights, K);
            if (index != -1) {
                heights[index]++;
                continue;
            }

            index  = find_min_right(heights, K);
            if (index != -1) {
                heights[index]++;
                continue;
            }

            heights[K]++;
        }

        return heights;
    }
};
-------------end of filethanks for reading-------------